//	--------------------------------------------------------------------
//	Copyright(C) 2006,2007 Zhao Yukun. All rights reserved.
//	This file is a part of the Xeres system.
//	Xeres 2007
//	Contact : xeres.engine@gmail.com
//	$(reservedInfo)
//	$(reservedDeclaration)
//	--------------------------------------------------------------------
///	@file	<fixed_space.h>
///	@path	~/src/lib/memory/
///	@date	2007/11/18
///	@desc	Fixed memory space for allocate small object.

#pragma once

#include "xeres.h"

#include <set>
#include <deque>

#include "lib/memory/aligned_space.h"

namespace xeres {

	/*!
		\class	fixed_space
		\brief	Use chunks to manage fixed space.
	*/
	template<
		size_t _Size ,
		typename _Allocator = aligned_fixed_space< byte , _Size , ALIGN_SIZE >
	> class fixed_space
	{
	private:

		// header size
		static const size_t HEADER_SIZE = ( sizeof(byte) * 31 ) + /* markers */ sizeof( byte ) /* free count */;

		// max cell count
		static const int MAX_CELL = 248;

		// cell size
		static const size_t CELL_SIZE = ALIGNOF( _Size * MAX_CELL , ALIGN_SIZE );

		// chunk size
		static const size_t CHUNK_SIZE = ALIGNOF( HEADER_SIZE + CELL_SIZE , ALIGN_SIZE );

	public:

		/// \ctor
		fixed_space( void )
		{
		}

		/// \dtor
		~fixed_space( void )
		{
			// Free all chunks.
			for( std::set< _Chunk * >::iterator it = m_chunks.begin() ; it != m_chunks.end() ; ++it )
			{
				_aligned_free( *it );
			}
		}

	//@ methods

		/*!
			\brief		Allocate object.
		*/
		void * allocate( void )
		{
			void * ptr = NULL;
			// See if any empty chunk exists.
			if( m_freeChunks.empty() )
			{
				ptr = new_chunk()->allocate();
				assert( ptr != NULL );
			}
			else
			{
				std::set< _Chunk * >::iterator it = m_freeChunks.begin();
				_Chunk * chunk = *it;
				// Use a free chunk to allocate.
				ptr = chunk->allocate();
				assert( ptr != NULL );

				// Full chunk?
				if( chunk->is_full() )
					m_freeChunks.erase( it );
			}
			return ptr;
		}

		/*!
			\brief		Deallocate object.
		*/
		void deallocate( void * cell )
		{
			_Chunk * chunk = which_chunk( cell );
			bool chunk_full = chunk->is_full();
			if( chunk == NULL )
			{
				// FIXME! report error
				assert( false );
			}
			chunk->deallocate( cell );
			if( chunk->is_empty() )
			{
				if( m_emptyChunks.size() > 3 )
				{
					// flush empty chunks
					for( size_t i = 0 ; i < m_emptyChunks.size() ; ++i )
					{
						m_chunks.erase( m_emptyChunks[i] );
						_aligned_free( m_emptyChunks[i] );
					}
					m_emptyChunks.clear();
				}
				// add empty chunk
				m_emptyChunks.push_back( chunk );
				assert( m_freeChunks.find( chunk ) != m_freeChunks.end() );
				m_freeChunks.erase( chunk );
			}
			else if( chunk_full )
			{
				m_freeChunks.insert( chunk );
			}
		}

	private:

		// chunks to store space
		struct _Chunk
		{
			// 31 bytes to mark used cells
			union
			{
				struct
				{
					byte		m_marks[31];
					byte		m_free;
				};
				long			m_longs[8];
				byte			m_bits[32];
			};

			byte				m_cells[1];

			// is empty
			bool is_empty( void ) const
			{
				return m_free == MAX_CELL;
			}

			// is full
			bool is_full( void ) const
			{
				return m_free == 0;
			}

			// which cell
			int which_cell( void * address ) const
			{
				return ((int)address - (int)(m_cells)) / _Size;
			}

			// mark
			void mark( int which_mark , int which_bit , bool marked )
			{
				// 0~248 bit
				if( marked )
				{
					_bittestandset( m_longs + which_mark , which_bit );
				}
				else
				{
					_bittestandreset( m_longs + which_mark , which_bit );
				}
			}

			// test bit
			bool test( int which_mark , int which_bit ) const
			{
				return _bittest( m_longs + which_mark , which_bit ) ? true : false;
			}

			// allocate
			void * allocate( void )
			{
				byte freeOld = m_free;
				assert( m_free > 0 );
				for( int m = 0 ; m < 8 ; ++m )
				{
					for( int b = 0 ; b < 32 ; ++b )
					{
						if( !test( m , b ) )
						{
							int index = m * 32 + b;
							if( index >= MAX_CELL )
							{
								assert(false);
								break;
							}

							mark( m , b , true );
							assert( m_free == freeOld );
							--m_free;
							return m_cells + index * _Size;
						}
					}
				}
				assert(false);
				return NULL;
			}

			// deallocate
			void deallocate( void * addr )
			{
				int cell = which_cell( addr );
				assert( cell < MAX_CELL && cell >= 0 );
				int which_mark = cell / 32;
				int which_bit = cell % 32;
				assert( test( which_mark , which_bit ) );
				mark( which_mark , which_bit , false );
				++m_free;
				assert( m_free <= MAX_CELL );
			}
		};

		// which chunk
		_Chunk * which_chunk( void * ptr )
		{
			std::set< _Chunk * >::iterator it = m_chunks.lower_bound( (_Chunk*)( (int)ptr - CHUNK_SIZE ) );
			if( it == m_chunks.end() )
				return NULL;
			return *it;
		}

		// new chunk
		_Chunk * new_chunk( void )
		{
			_Chunk * chunk = NULL;
			if( !m_emptyChunks.empty() )
			{
				// reuse empty chunk
				chunk = m_emptyChunks.back();
				m_emptyChunks.pop_back();
				m_freeChunks.insert( chunk );
			}
			else
			{
				chunk = static_cast<_Chunk*>( _aligned_malloc( CHUNK_SIZE , ALIGN_SIZE ) );
				memset( chunk , 0 , CHUNK_SIZE );
				chunk->m_free = MAX_CELL;
				m_chunks.insert( chunk );
				m_freeChunks.insert( chunk );
			}
			return chunk;
		}

	//@ data

		std::set< _Chunk * >		m_chunks;
		std::set< _Chunk * >		m_freeChunks;
		std::deque< _Chunk * >		m_emptyChunks;
	};

} // namespace xeres
